The present invention concerns the field of the processing of digital data with a view to applications such as the compression of digital data, the search for digital data, the comparison of digital data or the decompression of digital data. The invention concerns the processing of audiovisual data, and more generally any type of digital data. The aim of the invention is to reduce the processing time and the computing resource requirements with regard to both the computing power and the memory requirements.
The applications concern in particular but not exclusively the processing of images requiring a very large number of data to describe them. To reduce the transmission time and the size required for storage, the information is compressed by extracting the visual information that alone will be coded. This coded information must be located in an optimum fashion in terms of frequency and in space to allow optimum reproduction while avoiding any redundancy detrimental to the performance of the coding. For this purpose, using the wavelet transform technique is known, the coordinates of which constitute a vector lattice that is then subjected to a vector quantisation step.
The principle of vector quantisation (VQ) is to code a sequence of samples forming a vector instead of coding each of the samples individually. The coding is done by approximating the sequence to be coded by a vector belonging to a catalogue of forms usually referred to as a “codebook”. Each of the vectors of the catalogue of forms is indexed. During coding, it is the index of the vector closest to the sequence of samples to be coded that will be used to represent it.
The known solutions require the determination of each of the vectors, recording thereof in a memory and then execution of processing on all the vectors in order to count them. The vector base may require several gigabytes and the computing times for such a large base are lengthy. The aim of the invention is to propose a counting and indexing method avoiding these drawbacks. A quantisation method is known from article [1]. A lattice is a set of vectors in a space with dimension n forming an additive group, in the mathematical sense of the term. The book [2] describes such lattices in detail. International Patent Application WO9933185 is known in the prior art, concerning a coding method consisting of determining a vector, referred to as the leader, which comprises the same components as the quantised vector but in a predetermined order, and then determining the level or rank of the quantised vector in the formed set of vectors that have the same components as the leader and are, in the set, ordered in a predetermined manner. The method then consists in forming a code from firstly an index representing the leader thus determined and secondly the rank.
The main difficulty encountered for designing an algebraic vector quantiser for the compression is related to the problem of counting and indexing vectors in the regular lattice of points (which constitutes the quantisation dictionary). We present here the solutions that we have proposed for solving these problems in the case of a generalised Gaussian distribution source (such as for example the wavelet coefficients).
Algebraic Vector Quantisation
Quantisation has been studied for a few decades now and the work done has developed numerous results that are today conventional on the rate/distortion theory. In particular, it has been shown that vector quantisation (VQ) has numerous advantages compared with scalar quantisation (SQ) when fixed-length coding is required. In addition, the work by Shannon has shown that the performances of VQ are close to the optimum theoretical performances if the dimension n of the quantisation vectors is sufficiently large.
However, it is important to note that VQ may approach these optimum performances at the cost of a high computing complexity; a complexity that increases exponentially with the dimension of the vectors. Generally, VQ is performed using a non-structured dictionary constructed from statistical data representing the source (learning sequence). In this case, the complexity and the storage requirements due to the size of the dictionary may become prohibitive for compression applications. In addition, there exists a problem of robustness of the dictionary which, optimised for a given learning sequence, gives poor performance for an image outside the learning sequence. One solution for overcoming these problems is to use an n-dimensional structured VQ such as algebraic vector quantisation (AVQ) or vector quantisation on regular lattices of points.
As the vectors of the dictionary are forced to belong to a structured regular lattice, the performances of AVQ are in general inferior to those of non-structured VQ. However, in the majority of applications, this slight disadvantage is compensated for by the fact that, for AVQ, no dictionary needs to be generated or stored, and the coding complexity is reduced.
Quantisation by regular lattices of points may be seen as an extension of uniform scalar quantisation. As in the case of non-structured VQ, the term AVQ will be used in the rest of the document either to designate vector quantisation or to designate a vector quantiser. AVQ takes into account the spatial dependencies between the coefficients of the vectors and the gains in partitioning and form. Whatever the distribution of the source, AVQ is always more effective than SQ.
A regular lattice of points in Rn is composed of all the possible combinations of a set of linearly independent vectors ai that constitutes the base of the lattice {y|y=u1a1+u2a2+ . . . +unan} where the coefficients ui are integers. The partitioning of the space is then regular and depends only on the base vectors chosen. Each base defines a regular lattice of different points. AVQ offers the possibility of considerably reducing the computing and storage costs compared with a VQ design by means of algorithms based on the generalised Lloyd algorithm. Indeed, using the vectors of a regular lattice as quantisation values eliminates the operation of constructing a dictionary: the dictionary is constructed implicitly through the structure of the selected lattice. The article [1] describes fast quantisation algorithms that simply use counting operations and depend only on the dimension n of the vectors. In 1979, Gersho made the conjecture that, in the asymptotic case (that is to say for high rates), the rate/distortion performances of an AVQ are approximately optimum. However, although the AVQ is not mathematically optimum for low rates, the reduction in complexity afforded by such quantisers makes it possible to use large dimensions of vectors, which gives rise to better experimental performances for a given rate. Good rate/distortion performance can be obtained by combining AVQ with an entropic coder, which motivated a few works on AVQ in the field of wavelets. Many theoretical works on VQ have been carried out for Gaussian and Laplacian sources. Furthermore, in the case of generalised Gaussian sources with a decrease parameter of less than one, it was shown that the cubic lattice Zn was better in terms of rate/distortion than the lattice E8 and the Leech lattice. This result spurred on our work to combine AVQ with wavelet transform.